The present invention relates generally to communication networks and more specifically to systems and methods for rate-based scheduling.
High speed networks are designed to carry services with a wide range of quality-of-service (QoS) requirements. It is useful to define a hierarchy of traffic classes over which QoS requirements may be configured. FIG. 1 depicts an example of such a hierarchy. There are three levels. The bottom level or root is a node 102 defining a single physical interface over which traffic will be transmitted. The next level of hierarchy shows three logical interfaces 104, 106, 108. Logical interfaces may correspond to, e.g., virtual LANs (VLANs). A third level of hierarchy consists of classes. Here logical interface 104 has associated classes 110 and 112. Logical interface 106 has classes 114, 116, and 118. Logical interface 108 has associated classes 120 and 122. Each class has may represent, for example, a different customer.
Thus, all of the classes, logical interfaces, and physical interfaces are represented by nodes in a tree structure. The nodes corresponding to the classes are leaf nodes, i.e., they are furthest from the root node in the hierarchy. When packets arrive they are placed in a queue associated with a leaf node.
Each node in this hierarchy typically has a configured minimum rate, maximum rate, and excess bandwidth sharing weight. Each node is expected to be served by its parent node at least at its configured minimum service rate and up to its maximum configured rate. The excess service that can be given to a node above and beyond its minimum rate is proportional to its specified excess bandwidth sharing weight relative to the weights of its active non-empty peers that are simultaneously vying for excess service.
Furthermore, individual nodes can be configured as priority nodes. In FIG. 1, priority nodes are drawn with dashed lines. Priority nodes have higher scheduling preference than their siblings regardless of the other scheduling criteria. For example, voice traffic may be assigned to a priority class. The class hierarchies now being discussed are desired to have the property of priority propagation. This means that a priority indication can be passed on a per-packet basis from a node to its parent. Priority nodes do not typically have minimum and maximum rates or excess sharing weights but may have priority rates to be used in allocating transmission resources among sibling priority nodes.
The tree structure of FIG. 1 also represents a scheduling hierarchy that corresponds to the class hierarchy. The goal of the scheduling hierarchy is to determine the sequence of packet transmissions in such a way as to insure the satisfaction of the rate and priority settings of each node in the class hierarchy. Conceptually, the scheduling hierarchy performs as follows. The root node in the class hierarchy runs a one-layer scheduler to choose one of its children nodes. A chosen child in turn, runs its own one-layer scheduler that chooses one of its own children. This process continues until a “leaf” of the class hierarchy is reached.
Attributes of the children, such as the guaranteed rates and priorities of the children are actually stored in and managed by the parent's scheduler. From the perspective of the parent, the children nodes are schedule entries in the local scheduler.
In a representative implementation, the behavioral model of a scheduling node is as follows:
1) If at least one of the priority schedule entries is not empty, one of the priority entries must be chosen.
2) If all priority schedule entries are empty, then choose one of the schedule entries whose minimum rate has not yet been satisfied.
3) If all schedule entries with non-zero minimum rates have currently reached or exceeded their minimum rate, choose a schedule entry whose maximum rate has not yet been satisfied.
In a non-pipelined implementation, for each physical interface packet transmission opportunity, a scheduling decision is made that involves selecting a node from the lowest level of the hierarchy. A single scheduling decision involves traversal of scheduling nodes along a particular path through the tree. The choice of the branch to follow at each scheduling node is determined by a scheduling decision at each node: the next (child) scheduling node in the traversal is the one corresponding to the schedule entry chosen at the previous scheduling node. The result of this tree traversal is to select a packet from a queue associated with one of the leaf nodes.
Alternatively, a packet pipeline model can be used. The physical interface scheduling decision is made from among packet handles (pointers to queued packets) that have propagated to nodes at the level of hierarchy adjacent to the root. The root node picks a packet handle based on its scheduling criteria. The node that stored this packet handle then replaces it with a packet handle stored by one of its children, making a selection based on its own scheduling criteria. In this way, packet handles propagate downward from leaf nodes to the root.
Problems arise in applying the scheduling hierarchy to handling priority traffic. It is desirable to mandate the property referred to above as priority propagation so that priority traffic experiences low latency.
For example, when the root node arbitrates among its children, it may be that none of these children are configured with priority, but some of the descendants of these children are configured with priority and are non-empty. It is desirable therefore that the root chooses a child with non-empty priority descendant(s). In a purely rate-based scheduler, such functionality is unavailable, as each node arbitrates among its own children only based on the children's state and does not have any awareness of the existence of priority descendants beyond its own child layer. Hence, the scheduler may choose a branch of the tree with no priority traffic even though some other branch of the tree may contain non-empty priority nodes. This will cause extra undesirable delay for priority traffic.
Additionally, inaccuracies in the rate-based scheduler may further increase the latency of priority traffic and further exacerbate the inability to provide the necessary low latency to priority traffic. One typical scenario where the prior art rate-based schedulers fall short arises when a node with an active priority descendent must wait for a large number of siblings to be scheduled ahead of this node even if the other siblings have no priority traffic. If packet pipelining is used, the pipeline delay further contributes to undesired latency imposed on priority traffic. It would be desirable to have a scheduler that meets the following criteria:
1) Priority traffic is not delayed by competing non-priority traffic by more than the time duration needed to transmit one maximum length packet at the speed of the physical interface.
2) Multiple sibling priority levels are supported.
3) Different priority streams are scheduled in proportion to their priority rates to minimize per-flow jitter.
4) The excess-rate service that each entry receives over its minimum rate is shared according to the specified excess sharing weight.